public class Solution21 {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode first=new ListNode(-1,null);
        ListNode cur=first;
        while (list1!=null && list2!=null){
            if (list1.val<list2.val){
                cur.next=list1;
                cur=list1;
                list1=list1.next;
            }else{
                cur.next=list2;
                cur=list2;
                list2=list2.next;
            }
        }
        while (list1!=null){
            cur.next=list1;
            cur=list1;
            list1=list1.next;
        }
        while (list2!=null){
            cur.next=list2;
            cur=list2;
            list2=list2.next;
        }
        return first.next;
    }

    public static void main(String[] args) {
        System.out.println(new Solution21().mergeTwoLists(new ListNode(1,new ListNode(2,new ListNode(4))),new ListNode(1,new ListNode(3,new ListNode(4)))).next.next.next.val);
    }
}
